package p300;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Leetcode_315 {
    public static List<Integer> countSmaller(int[] nums) {
        List<int[]> res = new ArrayList<>();
        if (nums.length == 0) {
            return new ArrayList<>();
        }
        for (int i = 0; i < nums.length; i++) {
            int[] tmp = {nums[i], 0, i};
            res.add(tmp);
        }
        res = sort(res);
        Integer[] results = new Integer[nums.length];
        for (int[] xda : res) {
            results[xda[2]] = xda[1];
        }
        return Arrays.asList(results);
    }

    private static List<int[]> sort(List<int[]> res) {
        if (res.size() == 1) {
            return res;
        }
        int size = res.size() / 2;
        List<int[]> left = res.subList(0, size);
        List<int[]> right = res.subList(size, res.size());
        left = sort(left);
        right = sort(right);
        int i = 0, j = 0;
        List<int[]> r = new ArrayList<>();
        while (i < left.size() || j < right.size()) {
            if (j == right.size()) {
                r.add(i + j, left.get(i));
                i++;
                continue;
            }
            if (i == left.size()) {
                r.add(i + j, right.get(j));
                j++;
                continue;
            }
            if (left.get(i)[0] > right.get(j)[0]) {
                r.add(i + j, left.get(i));
                left.get(i)[1] = left.get(i)[1] + (right.size() - j);
                i++;
            } else {
                r.add(i + j, right.get(j));
                j++;
            }
        }
        return r;
    }

    public static void main(String[] args) {
        System.out.println(countSmaller(new int[]{1, 2, 3, 4, 7}));
    }
}
